๐Ÿ“‚ Tree(ํŠธ๋ฆฌ)

@Seongukbaek Posted May 27, 2022 ยท Updated May 27, 2022 ยท 4 min read

๐Ÿงท ํŠธ๋ฆฌ

๊ฐ’์„ ๊ฐ€์ง„ ๋…ธ๋“œ(Node)์™€ ์ด ๋…ธ๋“œ๋“ค์„ ์ด์–ด์ฃผ๋Š” ๊ฐ„์„ (Edge)๋กœ ์ด๋ฃจ์–ด์ง„ ์ž๋ฃŒ๊ตฌ์กฐ์ด๋‹ค.

ํŠธ๋ฆฌ๋ผ๋Š” ์ด๋ฆ„์ด ๋‚˜์˜จ ์ด์œ ?

: ์‹ค์ œ ๋‚˜๋ฌด๋ฅผ ๊ฑฐ๊พธ๋กœ ์„ธ์›Œ๋†“์€ ๋“ฏํ•œ ๋ชจ์–‘์„ ๋ณด์ด๊ธฐ ๋•Œ๋ฌธ์ด๋‹ค.

  • ๊ทธ๋ฆผ์—์„œ, ๋ฐ์ดํ„ฐ 1์„ ๊ฐ€์ง„ ๋…ธ๋“œ๊ฐ€ ๋ฃจํŠธ ๋…ธ๋“œ์ด๋‹ค.
  • ๋ชจ๋“  ๋…ธ๋“œ๋“ค์€ 0๊ฐœ ์ด์ƒ์˜ ์ž์‹ ๋…ธ๋“œ๋ฅผ ๊ฐ€์ง€๊ณ  ์žˆ์œผ๋ฉฐ, "๋ถ€๋ชจ-์ž์‹ ๊ด€๊ณ„"๋กœ ๋ถˆ๋ฆฐ๋‹ค.

์„ ํ˜• ์ž๋ฃŒ๊ตฌ์กฐ์—์„œ ๋ฐฐ์—ด์ด๋‚˜ ๋ฆฌ์ŠคํŠธ ๋“ฑ๋„ ์กด์žฌํ•˜์ง€๋งŒ, ํŠธ๋ฆฌ๊ฐ€ ๋‚˜์˜จ ์ด์œ ๋Š” ๋ญ˜๊นŒ?

  • ์ผ๋ฐ˜ ๋ฐฐ์—ด์—์„œ ์‚ฝ์ž…์ด๋‚˜ ์‚ญ์ œ๋ฅผ ํ•˜๋Š”๋ฐ O(N)O(N)์˜ ์‹œ๊ฐ„์ด ๊ฑธ๋ฆฐ๋‹ค.

    • ๋ฐฐ์—ด์˜ ์ฒซ๋ฒˆ์งธ ์›์†Œ์— ์‚ฝ์ž…ํ•˜๋Š” ๊ฒฝ์šฐ ๋‚˜๋จธ์ง€ ๋ชจ๋“  ์š”์†Œ๋“ค์„ ํ•œ ์นธ์”ฉ ๋’ค๋กœ ๋ฏธ๋ค„์•ผ ํ•˜๋ฏ€๋กœ ์ตœ์•…์˜ ๊ฒฝ์šฐ, O(N)O(N)์˜ ์‹œ๊ฐ„ ๋ณต์žก๋„๊ฐ€ ๋‚˜์˜จ๋‹ค.
  • ํ•˜์ง€๋งŒ ํŠธ๋ฆฌ๋Š” ํŽธํ–ฅ ํŠธ๋ฆฌ๊ฐ€ ์•„๋‹Œ ์ด์ƒ, O(logN)O(logN) ์ •๋„์˜ ์‹œ๊ฐ„์œผ๋กœ ์ค„์—ฌ์ง„๋‹ค.

๐Ÿชš ํŠน์ง•

  • Stack์ด๋‚˜ Queue์™€ ๊ฐ™์€ ์„ ํ˜• ๊ตฌ์กฐ๊ฐ€ ์•„๋‹Œ ๋น„์„ ํ˜• ์ž๋ฃŒ๊ตฌ์กฐ์ด๋‹ค.
  • ๊ณ„์ธต์  ๊ด€๊ณ„๋ฅผ ํ‘œํ˜„ํ•œ๋‹ค.
  • ๋ฃจํŠธ ๋…ธ๋“œ๋ฅผ ์ œ์™ธํ•œ ๋ชจ๋“  ๋…ธ๋“œ๋Š” ๋‹จ ํ•˜๋‚˜์˜ ๋ถ€๋ชจ ๋…ธ๋“œ๋งŒ์„ ๊ฐ–๋Š”๋‹ค.
  • ํŠธ๋ฆฌ์—๋Š” ์‚ฌ์ดํด์ด ์กด์žฌํ•  ์ˆ˜ ์—†๋‹ค. (๋งŒ์•ฝ ์‚ฌ์ดํด์ด ๋งŒ๋“ค์–ด์ง„๋‹ค๋ฉด, ๊ทธ๋ž˜ํ”„์ด๋‹ค.)
  • ๋ชจ๋“  ๋…ธ๋“œ๋Š” ์ž๋ฃŒํ˜•์œผ๋กœ ํ‘œํ˜„์ด ๊ฐ€๋Šฅํ•˜๋‹ค.
  • ๋ฃจํŠธ์—์„œ ํ•œ ๋…ธ๋“œ๋กœ ๊ฐ€๋Š” ๊ฒฝ๋กœ๋Š” ์œ ์ผํ•œ ๊ฒฝ๋กœ๋ฟ์ด๋‹ค.
  • ๋…ธ๋“œ์˜ ๊ฐœ์ˆ˜๊ฐ€ N๊ฐœ๋ฉด, ๊ฐ„์„ ์€ N-1๊ฐœ๋ฅผ ๊ฐ€์ง„๋‹ค.

๐Ÿชš ํŠธ๋ฆฌ ์ˆœํšŒ ๋ฐฉ์‹

ํŠธ๋ฆฌ์˜ ๋ฃจํŠธ๋ฅผ ๊ธฐ์ค€์œผ๋กœ ์ด 4๊ฐ€์ง€์˜ ์ˆœํšŒ ๋ฐฉ์‹์ด ์žˆ๋‹ค. ํŠธ๋ฆฌ๋Š” ์œ„ ๊ทธ๋ฆผ์„ ์‚ฌ์šฉํ•œ๋‹ค.

  1. ์ „์œ„ ์ˆœํšŒ(pre-order)

    • ๊ฐ ๋ฃจํŠธ๋ฅผ ์ˆœ์ฐจ์ ์œผ๋กœ ๋จผ์ € ๋ฐฉ๋ฌธํ•˜๋Š” ๋ฐฉ์‹์ด๋‹ค. (Root -> ์™ผ์ชฝ ์ž์‹ -> ์˜ค๋ฅธ์ชฝ ์ž์‹)
    • 1 -> 2 -> 4 -> 8 -> 9 -> 5 -> 10 -> 11 -> 3 -> 6 -> 13 -> 7 -> 14
  2. ์ค‘์œ„ ์ˆœํšŒ(in-order)

    • ์™ผ์ชฝ ํ•˜์œ„ ํŠธ๋ฆฌ๋ฅผ ๋ฐฉ๋ฌธํ•œ ํ›„ ๋ฃจํŠธ๋ฅผ ๋ฐฉ๋ฌธํ•˜๋Š” ๋ฐฉ์‹์ด๋‹ค. (์™ผ์ชฝ ์ž์‹ -> Root -> ์˜ค๋ฅธ์ชฝ ์ž์‹)
    • 8 -> 4 -> 9 -> 2 -> 10 -> 5 -> 11 -> 1 -> 6 -> 13 -> 3 -> 14 -> 7
  3. ํ›„์œ„ ์ˆœํšŒ(post-order)

    • ์™ผ์ชฝ ํ•˜์œ„ ํŠธ๋ฆฌ๋ถ€ํ„ฐ ํ•˜์œ„๋ฅผ ๋ชจ๋‘ ๋ฐฉ๋ฌธํ•œ ํ›„ ๋ฃจํŠธ๋ฅผ ๋ฐฉ๋ฌธํ•˜๋Š” ๋ฐฉ์‹์ด๋‹ค. (์™ผ์ชฝ ์ž์‹ -> ์˜ค๋ฅธ์ชฝ ์ž์‹ -> Root)
    • 8 -> 9 -> 4 -> 10 -> 11 -> 5 -> 2 -> 13 -> 6 -> 14 -> 7 -> 3 -> 1
  4. ๋ ˆ๋ฒจ ์ˆœํšŒ(level-order)

    • ๋ฃจํŠธ๋ถ€ํ„ฐ ๊ณ„์ธต๋ณ„๋กœ ๋ฐฉ๋ฌธํ•˜๋Š” ๋ฐฉ์‹์ด๋‹ค.
    • 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 11 -> 12 -> 13 -> 14

๐Ÿชš ๊ตฌํ˜„

ํŠธ๋ฆฌ์˜ ๊ตฌํ˜„์„ ์œ„ํ•ด์„œ๋Š” ์•„๋ž˜์˜ ์ •๋ณด๋“ค์ด ํ•„์š”ํ•˜๋‹ค.

  1. ๋ฐ์ดํ„ฐ์™€ ์—ฐ๊ฒฐ ์ƒํƒœ๋ฅผ ์ €์žฅํ•  ํด๋ž˜์Šค ๊ณต๊ฐ„(=๋…ธ๋“œ) ์ƒ์„ฑ
  2. ๊ฐ๊ฐ์˜ ๋…ธ๋“œ๋“ค์— ๊ฐ’ ์ €์žฅ
  3. ๋…ธ๋“œ ๊ฐ„ ์—ฐ๊ฒฐ ์ƒํƒœ ์ •์˜
class Node { Node left; Node right; String value; public Node(String value) { this.left = null; this.right = null; this.value = value; } }
  • ๊ฐ ๋…ธ๋“œ๋“ค์€ ๊ฐ’๊ณผ, ์™ผ์ชฝ, ์˜ค๋ฅธ์ชฝ ์ž์‹ ๋…ธ๋“œ๋ฅผ ๊ฐ€์ง„๋‹ค.
class Tree { Node root; int size = 0; }
  • ํŠธ๋ฆฌ๋Š” ๋ฃจํŠธ ๋…ธ๋“œ์™€, ๊ทธ ํฌ๊ธฐ ์ •๋ณด๋ฅผ ๊ฐ€์ง„๋‹ค.

๐Ÿ“• ์ฐธ๊ณ 

@Seongukbaek
๋ฐฐ์šฐ๊ณ  ์ •๋ฆฌํ•˜๊ณ  ๊ณต์œ ํ•˜๋Š” ๋Œ€ํ•™์ƒ ๋ฐฑ์„ฑ์šฑ์ž…๋‹ˆ๋‹ค ๐Ÿ˜€